package cn.nit.algorithm.experiment;

/**
 * @author 刘祥棋
 * @version 0.0
 * @date 2021/6/4 7:42
 * 求解n皇后
 */


import java.util.Scanner;

public class Experiment8 {
    int N=20;                       //最多皇后个数
    int[] q=new int[N];             //存放皇后所在列数
    int count=0;                    //累计解个数
    public String totalString = "";

//    public static void main(String[] args) {
//        System.out.print("皇后问题(n<20) n=");
//        int n=new Scanner(System.in).nextInt();
//        if(n>20)
//            System.out.println("n值太大，不能求解");
//        else {
//            System.out.println(n+"皇后问题求解如下：");
//            Experiment8 experiment = new Experiment8();
//            experiment.queen(1,n);                      //放置皇1~n后
//        }
//    }

    public String runMain(int n){
        if(n>20) {
            System.out.println("n值太大，不能求解");
            totalString += "n值太大，不能求解<br>";
        }
        else {
            System.out.println(n+"皇后问题求解如下：");
            totalString+=n+"皇后问题求解如下：<br>";
            queen(1,n);                      //放置皇1~n后
        }
        return totalString;
    }

    public void dispasolution(int n) {         //输出n皇后问题的一个解
        System.out.print("   第"+(++count)+"个解");
        totalString+="   第"+(++count)+"个解";
        for(int i=1;i<=n;i++) {
            System.out.print("("+i+","+q[i]+")");
            totalString+="("+i+","+q[i]+")";
        }
        System.out.print("\n");
        totalString+="<br>";
    }

    public boolean place(int i,int j) {       //测试（i,j）位置能否摆放皇后
        if(i==0)                              //第一个皇后总是可以放置
            return true;
        int k=1;
        while(k<i) {                          //k=1~i-1是已经放置了皇后的行
            if((q[k]==j)||(Math.abs(q[k]-j)==Math.abs(i-k)))
                return false;
            k++;
        }
        return true;
    }

    public void queen(int i,int n) {          //放置的1~i皇后
        if(i>n)
            dispasolution(n);                 //所有皇后防止结束
        else {
            for(int j=1;j<=n;j++)             //在第i行上试探每一个列j
                if(place(i,j)) {              //在第i行上找到一个合适的位置（i，j)
                    q[i]=j;
                    queen(i+1, n);
                }
        }
    }
}
